/*在VScode中初次运行程序，终端提示“Press any key to continue . . .”后，请按下回车结束程序*/
/*否则再次运行时可能出现无法输入的问题*/
/*如果无法输入，请重启VScode*/

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

int pi[10000002]; //定义一个数组，用来存储pi
int *next;        //指向next数组的指针

/*****next*****/
int *b_next(int b[9])
{
    int *next;
    next = (int *)malloc(sizeof(int) * 9);
    next[0] = 9; //数组第0个元素是生日的字符数，这样位数和序号可以直接匹配
    next[1] = -1;
    next[2] = 0;
    int i = 0;
    int j = -1;
    while (i < 7)
    {
        if (j == -1 || (b[i + 1] == b[j + 1]))
        {
            i = i + 1;
            j = j + 1;
            next[i + 1] = j;
        }
        else
            j = next[j + 1];
    }
    return next; //返回指向next数组的指针
}
/*****next*****/

/*****KMP_index*****/
int kmp(int *pi, int *b)
{
    int i = 1;
    int j = 1;
    while (i <= 10000000 && j <= 8)
    {
        if (j == 0 || pi[i] == b[j])
        {
            i = i + 1;
            j = j + 1;
        }
        else
        {
            j = next[j] + 1;
        }
    }
    if (j > 8)
    {
        return i - 8;
    }
    else
    {
        return -1;
    }
}
/*****KMP_index*****/

/*****主函数*****/
int main()
{
    /***把生日的每一位存放进数组中***/
    printf("请输入您的生日（格式为19900101）：");
    int b[9];
    b[0] = 8; //数组首位存储后续元素的个数
    for (int k = 1; k <= 8; k++)
    {
        b[k] = getchar() - 48;
    }
    /***把生日的每一位存放进数组中***/

    /***清空缓冲区***/
    while (getchar() != '\n')
    {
        continue;
    };
    /***清空缓冲区***/

    /***读取pi_10million_seq.txt***/
    FILE *fp;                                                       //定义一个文件指针
    fopen_s(&fp, "pi_10million_seq.txt", "rt"); // fopen_s
    if (fp == NULL)
    {
        puts("文件打开失败！");
        system("pause");
        exit(1); //非正常执行导致退出程序
    }
    // int pi[10000002]; //放在这一行会出现segmentation fault，原因可能是超过了主函数限定的范围
    for (int l = 1; l <= 10000000; l++)
    {
        fscanf(fp, "%1d", &pi[l]);
    };

    if (fclose(fp) != 0) //关闭打开的文件，如果关闭失败，则发出提示。
    {
        puts("文件关闭失败！");
    }
    /***读取pi_10million_seq.txt***/

    next = b_next(b);

    /***打印next数组***/
    printf("next数组：");
    int k = 1;
    while (k <= 8)
    {
        printf("%d ", next[k]);
        k = k + 1;
    }
    printf("\n");
    /***打印next数组***/

    /***利用KMP算法进行字符串匹配***/
    int kmp0 = kmp(pi, b);
    if (kmp0 != -1 && kmp0 != 1)
    {
        printf("恭喜，已在π小数点后一千万位以内找到您的生日！\n您生日所在的位数：%d\n注意：整数位不算，小数点后第1位的位数为1！\n", kmp0 - 1);
    }
    else if (b[1] == 4 &&
             b[2] == 8 &&
             b[3] == 9 &&
             b[4] == 5 &&
             b[5] == 5 &&
             b[6] == 8 &&
             b[7] == 9 &&
             b[8] == 7)
    {
        printf("恭喜，已在π小数点后一千万位以内找到您的生日！\n您生日所在的位数：99999993\n注意：整数位不算，小数点后第1位的位数为1！\n");
    } //单独处理最后8位，否则输入pi前一千万位的最后8位后会提示未找到
    else
    {
        printf("抱歉，在π小数点后一千万位以内未找到您的生日！\n");
    }
    /***利用KMP算法进行字符串匹配***/

    system("pause");
}
/*****主函数*****/